
module es {
    export class SortUtils {

        //defaullt compare function
        protected static defaultCompareFn(a, b) {
            return a - b;
        }

        /**
         * Sort array elements，
         * @param list any type array
         * @param compareFn Numerical comparison is used by default, { -1, 0 , 1 }
         */
        public static sort<T>(list: T[], compareFn?: (a: T, b: T) => number) {
            let fn = compareFn || SortUtils.defaultCompareFn;
            SortUtils._sort(list, 0, list.length - 1, fn);
        }

        //quick_sort
        protected static _sort<T>(q: T[], l: number, r: number, fn) {

            if (l >= r) return;
            let x = q[l], i = l - 1, j = r + 1;
            while (i < j) {
                do i++; while (fn(q[i], x) < 0);
                do j--; while (fn(q[j], x) > 0);
                if (i < j) {
                    let temp: T = q[i];
                    q[i] = q[j];
                    q[j] = temp;
                }
            }
            SortUtils._sort(q, l, j, fn);
            SortUtils._sort(q, j + 1, r, fn);
        }

    }
}